Skew Heap
Operations
全順序集合の$ n要素の部分多重集合を扱う.
空間計算量$ \Theta(n)
$ \mathtt{new}()
空のヒープを作成する.
時間計算量$ \Theta(1)
$ \mathtt{peek}()
ヒープの最小の要素を返す.
時間計算量$ \Theta(1)
$ \mathtt{pop}()
ヒープの最小の要素を削除して返す.
時間計算量$ \Omicron(\log n) \ \rm amortized
$ \mathtt{insert}(x)
ヒープに要素$ xを追加する.
時間計算量$ \Omicron(\log n) \ \rm amortized
$ \mathtt{meld}(h)
ヒープ$ hの要素をすべて追加する.
時間計算量$ \Omicron(\log n) \ \rm amortized
Summary
融合可能なヒープ (meldable heap) の一つ
heap property を満たす自由な形の二分木によって表現される.
$ \mathtt{meld}が基本的な操作で，$ \mathtt{insert}や$ \mathtt{pop}は$ \mathtt{meld}を用いて実装できる
$ \mathtt{insert}(x): 単一のノード$ xからなるヒープを作成し, $ \mathtt{meld}
$ \mathtt{pop}(x): 根の要素を取り出して左右の子同士を$ \mathtt{meld}
$ \mathtt{meld}は右の子をたどるパスをマージし, 最後にパス上のノードについて子を swap する.
References
Notes
Implementations